//Sun Jun 12 23:58:56 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

typedef pair <pair<int, int>, pair<int, int> > State;
#define mp(a,b,c,d) make_pair(make_pair(a,b),make_pair(c,d))

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

class BombMan {
public:
	bool checkBound(int x, int y){
		return x>=0 && x<M && y>=0 && y<N;
	}
	int shortestPath(vector <string>, int);
	int grid[51][51][101];
	int M;
	int N;
};

int BombMan::shortestPath(vector <string> maze, int bombs) {
	M = maze.size();
	N = maze[0].size();
	memset(grid, -1, sizeof(grid));
	priority_queue<State> q;
	for(int i=0; i<M; i++)
		for(int j=0; j<N; j++){
			if(maze[i][j]=='B'){
				q.push(mp(0, bombs, i, j));
				grid[i][j][bombs] = 0;
			}
		}
	while(!q.empty()){
		State tmp = q.top();
		q.pop();
		int cost = -tmp.first.first;
		int b = tmp.first.second;
		int x = tmp.second.first;
		int y = tmp.second.second;
		if(grid[x][y][b] < cost) continue;
		if(maze[x][y] == 'E') return cost;
		
		for(int i=0; i<4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(!checkBound(xx, yy)) continue;
			if(maze[xx][yy]!='#' && (grid[xx][yy][b] > cost + 1 || grid[xx][yy][b] == -1)){
				grid[xx][yy][b] = cost + 1;
				q.push(mp(-cost-1, b, xx, yy));
			}
			if(maze[xx][yy]=='#' && (grid[xx][yy][b-1] > cost + 3 || grid[xx][yy][b-1] == -1) && b>0){
				grid[xx][yy][b-1] = cost + 3;
				q.push(mp(-cost-3, b-1, xx, yy));
			}
		}
	}
	return -1;
}

//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
